Search for: All records

Finding optimal bipartite matchings—e.g., matching medical students to hospitals for residency, items to buyers in an auction, or papers to reviewers for peer review—is a fundamental combinatorial optimization problem. We found a distributed algorithm for computing matchings by studying the development of the neuromuscular circuit. The neuromuscular circuit can be viewed as a bipartite graph formed between motor neurons and muscle fibers. In newborn animals, neurons and fibers are densely connected, but after development, each fiber is typically matched (i.e., connected) to exactly one neuron. We cast this synaptic pruning process as a distributed matching (or assignment) algorithm, where motor neurons “compete” with each other to “win” muscle fibers. We show that this algorithm is simple to implement, theoretically sound, and effective in practice when evaluated on real-world bipartite matching problems. Thus, insights from the development of neural circuits can inform the design of algorithms for fundamental computational problems. 

Abstract Catastrophic forgetting remains an outstanding challenge in continual learning. Recently, methods inspired by the brain, such as continual representation learning and memory replay, have been used to combat catastrophic forgetting. Associative learning (retaining associations between inputs and outputs, even after good representations are learned) plays an important function in the brain; however, its role in continual learning has not been carefully studied. Here, we identified a two-layer neural circuit in the fruit fly olfactory system that performs continual associative learning between odors and their associated valences. In the first layer, inputs (odors) are encoded using sparse, high-dimensional representations, which reduces memory interference by activating nonoverlapping populations of neurons for different odors. In the second layer, only the synapses between odor-activated neurons and the odor’s associated output neuron are modified during learning; the rest of the weights are frozen to prevent unrelated memories from being overwritten. We prove theoretically that these two perceptron-like layers help reduce catastrophic forgetting compared to the original perceptron algorithm, under continual learning. We then show empirically on benchmark data sets that this simple and lightweight architecture outperforms other popular neural-inspired algorithms when also using a two-layer feedforward architecture. Overall, fruit flies evolved an efficient continual associative learning algorithm, and circuit mechanisms from neuroscience can be translated to improve machine computation. 

Sparse coding can improve discrimination of sensory stimuli by reducing overlap between their representations. Two factors, however, can offset sparse coding’s benefits: similar sensory stimuli have significant overlap and responses vary across trials. To elucidate the effects of these 2 factors, we analyzed odor responses in the fly and mouse olfactory regions implicated in learning and discrimination—the mushroom body (MB) and the piriform cortex (PCx). We found that neuronal responses fall along a continuum from extremely reliable across trials to extremely variable or stochastic. Computationally, we show that the observed variability arises from noise within central circuits rather than sensory noise. We propose this coding scheme to be advantageous for coarse- and fine-odor discrimination. More reliable cells enable quick discrimination between dissimilar odors. For similar odors, however, these cells overlap and do not provide distinguishing information. By contrast, more unreliable cells are decorrelated for similar odors, providing distinguishing information, though these benefits only accrue with extended training with more trials. Overall, we have uncovered a conserved, stochastic coding scheme in vertebrates and invertebrates, and we identify a candidate mechanism, based on variability in a winner-take-all (WTA) inhibitory circuit, that improves discrimination with training. 

Abstract Keeping track of the number of times different stimuli have been experienced is a critical computation for behavior. Here, we propose a theoretical two-layer neural circuit that stores counts of stimulus occurrence frequencies. This circuit implements a data structure, called a count sketch , that is commonly used in computer science to maintain item frequencies in streaming data. Our first model implements a count sketch using Hebbian synapses and outputs stimulus-specific frequencies. Our second model uses anti-Hebbian plasticity and only tracks frequencies within four count categories (“1-2-3-many”), which trades-off the number of categories that need to be distinguished with the potential ethological value of those categories. We show how both models can robustly track stimulus occurrence frequencies, thus expanding the traditional novelty-familiarity memory axis from binary to discrete with more than two possible values. Finally, we show that an implementation of the “1-2-3-many” count sketch exists in the insect mushroom body. 

Feedback control is used by many distributed systems to optimize behaviour. Traditional feedback control algorithms spend significant resources to constantly sense and stabilize a continuous control variable of interest, such as vehicle speed for implementing cruise control, or body temperature for maintaining homeostasis. By contrast, discrete-event feedback (e.g. a server acknowledging when data are successfully transmitted, or a brief antennal interaction when an ant returns to the nest after successful foraging) can reduce costs associated with monitoring a continuous variable; however, optimizing behaviour in this setting requires alternative strategies. Here, we studied parallels between discrete-event feedback control strategies in biological and engineered systems. We found that two common engineering rules—additive-increase, upon positive feedback, and multiplicative-decrease, upon negative feedback, and multiplicative-increase multiplicative-decrease—are used by diverse biological systems, including for regulating foraging by harvester ant colonies, for maintaining cell-size homeostasis, and for synaptic learning and adaptation in neural circuits. These rules support several goals of these systems, including optimizing efficiency (i.e. using all available resources); splitting resources fairly among cooperating agents, or conversely, acquiring resources quickly among competing agents; and minimizing the latency of responses, especially when conditions change. We hypothesize that theoretical frameworks from distributed computing may offer new ways to analyse adaptation behaviour of biology systems, and in return, biological strategies may inspire new algorithms for discrete-event feedback control in engineering. 

Modern plant phenotyping requires tools that are robust to noise and missing data, while being able to efficiently process large numbers of plants. Here, we studied the skeletonization of plant architectures from 3D point clouds, which is critical for many downstream tasks, including analyses of plant shape, morphology, and branching angles. Specifically, we developed an algorithm to improve skeletonization at branch points (forks) by leveraging the geometric properties of cylinders around branch points. We tested this algorithm on a diverse set of high-resolution 3D point clouds of tomato and tobacco plants, grown in five environments and across multiple developmental timepoints. Compared to existing methods for 3D skeletonization, our method efficiently and more accurately estimated branching angles even in areas with noisy, missing, or non-uniformly sampled data. Our method is also applicable to inorganic datasets, such as scans of industrial pipes or urban scenes containing networks of complex cylindrical shapes. 

Creating a routing backbone is a fundamental problem in both biology and engineering. The routing backbone of the trail networks of arboreal turtle ants (Cephalotes goniodontus) connects many nests and food sources using trail pheromone deposited by ants as they walk. Unlike species that forage on the ground, the trail networks of arboreal ants are constrained by the vegetation. We examined what objectives the trail networks meet by comparing the observed ant trail networks with networks of random, hypothetical trail networks in the same surrounding vegetation and with trails optimized for four objectives: minimizing path length, minimizing average edge length, minimizing number of nodes, and minimizing opportunities to get lost. The ants’ trails minimized path length by minimizing the number of nodes traversed rather than choosing short edges. In addition, the ants’ trails reduced the opportunity for ants to get lost at each node, favoring nodes with 3D configurations most likely to be reinforced by pheromone. Thus, rather than finding the shortest edges, turtle ant trail networks take advantage of natural variation in the environment to favor coherence, keeping the ants together on the trails. 

Abstract Motivation Developing methods to efficiently analyze 3D point cloud data of plant architectures remain challenging for many phenotyping applications. Here, we describe a tool that tackles four core phenotyping tasks: classification of cloud points into stem and lamina points, graph skeletonization of the stem points, segmentation of individual lamina and whole leaf labeling. These four tasks are critical for numerous downstream phenotyping goals, such as quantifying plant biomass, performing morphological analyses of plant shapes and uncovering genotype to phenotype relationships. The Plant 3D tool provides an intuitive graphical user interface, a fast 3D rendering engine for visualizing plants with millions of cloud points, and several graph-theoretic and machine-learning algorithms for 3D architecture analyses. Availability and implementation P3D is open-source and implemented in C++. Source code and Windows installer are freely available at https://github.com/iziamtso/P3D/. Contact iziamtso@ucsd.edu or navlakha@cshl.edu Supplementary information Supplementary data are available at Bioinformatics online. 

Numerous types of biological branching networks, with varying shapes and sizes, are used to acquire and distribute resources. Here, we show that plant root and shoot architectures share a fundamental design property. We studied the spatial density function of plant architectures, which specifies the probability of finding a branch at each location in the 3-dimensional volume occupied by the plant. We analyzed 1645 root architectures from four species and discovered that the spatial density functions of all architectures are population-similar. This means that despite their apparent visual diversity, all of the roots studied share the same basic shape, aside from stretching and compression along orthogonal directions. Moreover, the spatial density of all architectures can be described as variations on a single underlying function: a Gaussian density truncated at a boundary of roughly three standard deviations. Thus, the root density of any architecture requires only four parameters to specify: the total mass of the architecture and the standard deviations of the Gaussian in the three x , y , z growth directions. Plant shoot architectures also follow this design form, suggesting that two basic plant transport systems may use similar growth strategies.